package com.duoduo.深度广度优先;

import com.duoduo.Node;

/**
 * @program: algorithm
 * @description: 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *
 *  
 *
 * 为了让您更好地理解问题，以下面的二叉搜索树为例：
 *
 *
 * @author: chaidl  ！  中序遍历
 * @create: 2022-03-02 16:43
 */
public class 二叉搜索树与双向链表 {
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if (root==null){
            return null;
        }
        dfs(root);
        head.left=pre;
        pre.right=head;
        return head;
    }
    //深度优先搜索
    public void dfs(Node cur) {
        if (cur==null){
            return;
        }
    //    先遍历左子树
        dfs(cur.left);
    //    如果当前节点的左边为空，表示已经是根节点
        if (pre != null){
            pre.right=cur;
        }else {
            head=cur;
        }
        cur.left=pre;
        pre=cur;
        dfs(cur.right);
    }
}
